class Solution {
public:
    /*
    大根堆存较小的一半     小根堆存较大的一半
    大根堆.size()-小根堆的.size()=1或者0;
    */
    priority_queue<int> maxheap;
    priority_queue<int,vector<int>,greater<int>> minheap;
    void Insert(int num) {
        //先无脑插入大根堆
        maxheap.push(num);
        //大根堆的元素比小根堆的元素多了
        //把大根堆中堆顶加入到小根堆中
         if(maxheap.size()-minheap.size()>1)
         {
             minheap.push(maxheap.top());
             maxheap.pop();
         }
        //如果大根堆中的根大于小根堆的根
        //需要交换
        while(minheap.size()&&maxheap.top()>minheap.top())
        {
            int maxval=maxheap.top(),minval=minheap.top();
            maxheap.pop();
            minheap.pop();
            maxheap.push(minval);
            minheap.push(maxval);
        }
    }

    double GetMedian() { 
        //奇数个元素
        if((maxheap.size()+minheap.size())%2==1)
            return maxheap.top();
        //偶数
        else
            return (maxheap.top()+minheap.top())/2.0;
    }

};